#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
    int minPathSum(vector<vector<int> > &grid) 
	{
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		if(grid.empty() || grid[0].empty())
			return 0;
		size_t m = grid.size(), n = grid[0].size();

		vector<vector<int> > sums(m);
		for(size_t i=0;i<m;i++)
			sums[i] = vector<int>(n);

		sums[0][0] = grid[0][0];
		for(size_t i=1;i<n;i++)
			sums[0][i] = sums[0][i-1]+grid[0][i];
		for(size_t i=1;i<m;i++)
			sums[i][0] = sums[i-1][0] + grid[i][0];

		for(size_t i=1;i<m;i++)
			for(size_t j=1;j<n;j++)
			{
				sums[i][j] = grid[i][j] + min(sums[i][j-1],sums[i-1][j]);
			}

		return sums[m-1][n-1];
    }
};

#endif